package com.wang.sort3;

import java.util.HashSet;

/**
 * @Author: along
 * @Create: 2021/4/21
 * @Description:最小放灯个数
 */
public class Demo03_Light {

        public static int minLight1(String road) {
            if (road == null || road.length() == 0) {
                return 0;
            }
            return process(road.toCharArray(), 0, new HashSet<>());
        }
        //str[index...]位置，自由选择是否放灯
        //str[0...index - 1]已经做完了决定，放了灯的位置存在lights中
        //要求选出所以能照亮 . 的方案，并且在有效方案中返回最少需要灯的个数
        public static int process(char[] str, int index, HashSet<Integer> lights) {
            if (index == str.length) {//结束的时候
                for (int i = 0; i < str.length; i++) {
                    if (str[i] != 'X') {//当前位置是点
                        if (!lights.contains(i - 1) && !lights.contains(i) && !lights.contains(i + 1)) {
                            return Integer.MAX_VALUE;
                        }
                    }
                }
                return lights.size();
            } else {//str还没结束
                //index   无论是X或 . 该位置不放灯
                int no = process(str, index + 1, lights);
                int yes = Integer.MAX_VALUE;
                if (str[index] == '.') {
                    lights.add(index);
                    yes = process(str, index + 1, lights);
                    lights.remove(index);//还原
                }
                return Math.min(no, yes);
            }
        }

        public static int minLight2(String road) {
            char[] str = road.toCharArray();
            int index = 0;
            int light = 0;
            while (index < str.length) {
                if (str[index] == 'X') {
                    index++;
                } else {
                    light++;
                    if (index + 1 == str.length) {
                        break;
                    } else {
                        if (str[index + 1] == 'X') {
                            index = index + 2;
                        } else {
                            index = index + 3;
                        }
                    }
                }
            }
            return light;
        }

        // for test
        public static String randomString(int len) {
            char[] res = new char[(int) (Math.random() * len) + 1];
            for (int i = 0; i < res.length; i++) {
                res[i] = Math.random() < 0.5 ? 'X' : '.';
            }
            return String.valueOf(res);
        }

        public static void main(String[] args) {
            int len = 20;
            int testTime = 100000;
            for (int i = 0; i < testTime; i++) {
                String test = randomString(len);
                int ans1 = minLight1(test);
                int ans2 = minLight2(test);
                if (ans1 != ans2) {
                    System.out.println("oops!");
                }
            }
            System.out.println("finish!");
        }
}
